package com.fe.class01;

/**
 * @Description 在一个无序数组中, 值有可能正, 负, 或者零, 数组中任意两个相邻的数一定不相等.
 * 定义局部最小: 1.长度为1，arr[0]就是局部最小；
 * 2.数组的开头，如果arr[0] < arr[1] ，arr[0]被定义为局部最小。
 * 3.数组的结尾，如果arr[N-1] < arr[N-2] ，arr[N-1]被定义为局部最小。
 * 任何一个中间位置i, 即数组下标1~N-2之间, 必须满足arr[i-1] < arr[i] <arr[i+1] ,叫找到一个局部最小。
 * 请找到任意一个局部最小并返回。
 * @Author sosuke :-)
 * @Date 2021/12/2 07:15
 */
public class Code07_BSPartLess {

    public static int findPartlyLessIndex (int[] arr) {
        if (null == arr || arr.length == 0) return -1;
        if (arr.length == 1 || arr[0] < arr[1]) return 0;
        if (arr[arr.length - 2] > arr[arr.length - 1]) return arr.length - 1;

        // 已经排除了首末两位，且初始时是下降的，末尾时是上扬的，中间必有局部最小值
        int L = 1;
        int R = arr.length - 2;
        while (L < R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] > arr[mid - 1]) { // 中间上扬，左侧必有局部最小值，R左移
                R = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) { // 中间下降，右侧必有局部最小值，L右移
                L = mid + 1;
            } else {
                return mid;
            }
        }
        return L;
    }

}
